class Solution
{
public:
    int maxValue(int n, int index, int maxSum)
    {
        int left = 1;
        int right = maxSum;
        while (left < right)
        {
            int mid = (left + right + 1) / 2;
            long long sum = getSum(n, index, mid);
            if (sum > maxSum)
            {
                right = mid - 1;
            }
            else
            {
                left = mid;
            }
        }
        return left;
    }

    long long getSum(int n, int index, long long indexVal)
    {
        long long leftLen = index;
        long long rightLen = n - index - 1;
        long long result = indexVal;
        if (indexVal <= leftLen + 1)
        {
            result += indexVal * (indexVal - 1) / 2;
            result += leftLen - indexVal + 1;
        }
        else
        {
            long long leftBeginVal = indexVal - leftLen;
            result += (leftBeginVal + indexVal - 1) * leftLen / 2;
        }
        if (indexVal <= rightLen + 1)
        {
            result += indexVal * (indexVal - 1) / 2;
            result += rightLen - indexVal + 1;
        }
        else
        {
            long long rightBeginVal = indexVal - rightLen;
            result += (rightBeginVal + indexVal - 1) * rightLen / 2;
        }
        return result;
    }
};